/*
现在有一个有序数组（从小到大，数组长度 0 < n < 1000000）如何快速寻找我们想要的数在哪个位置，如果存在请返回下标，不存在返回-1即可。
二分查找法，也叫折半查找.二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；
如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x. 时间复杂度即是while循环的次数。
使用二分搜索，前提是数字是有序的，如果无序，二分查找没有意义。
 */
package com.test.binarySearch;

public class Main {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 4, 5, 6, 7, 10, 12, 14, 20, 22, 26};
        System.out.println(binarySearch(arr, 5));
    }

    public static int binarySearch(int[] array, int target){
        int start = 0, end = array.length - 1;
        while(start <= end){
            int mid = (start + end + 1) /2;  //这里加1不加1都可以
            if (target == array[mid]){
                return mid;
            }
            if (target < array[mid]){
                end = mid -1;  //如果target比中间的值小，说明target在前半部分，end的值变为中间的数字前一位。
            }
            if (target > array[mid]){
                start = mid +1;  //如果target比中间的数字大，说明target在后半部分，start的值改为从中间部分的下一位开始。
            }
        }
        return -1;  //如果没有查找到，返回-1
    }
}
